package alice.exercise.leetcode.util;

import java.util.Arrays;

/**
 * @author Alice
 * @since 2023-02-28 星期二 14:18
 */
public final class SortUtil {
  private SortUtil() {
  }

  public static void bubbleSort(int[] arr) {
    int len = arr.length;
    int tmp;
    for (int i = 0; i < len - 1; i++) {
      for (int j = 0; j < len - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          tmp = arr[j + 1];
          arr[j + 1] = arr[j];
          arr[j] = tmp;
        }
      }
    }
  }

  public static void quickSort(int[] arr) {
    doQuickSort(arr, 0, arr.length - 1);
  }

  private static void doQuickSort(int[] arr, int start, int end) {
    if (start >= end) {
      return;
    }
    int i = start, j = end;
    int base = arr[start];
    int tmp;
    while (i < j) {
      if (arr[j] >= base) {
        j--;
      } else if (arr[i] <= base) {
        i++;
      } else {
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        i++;
        j--;
      }
    }
    tmp = arr[0];
    arr[0] = arr[i];
    arr[i] = tmp;
    doQuickSort(arr, 0, i - 1);
    doQuickSort(arr, i + 1, arr.length - 1);
    System.out.println("------ " + Arrays.toString(arr));
  }
}
